package com.scaffold.service;

import java.util.*;

/**
 * @author PC
 * @version 1.0
 * @description: TODO
 * @date 2024/10/18 10:05
 */
public class Demo {

    public static void main(String[] args) {
        int i = climbStairs(10);
        System.out.println(i);
    }

    public static int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    public static int mySqrt(int x) {
        long a = 0;
        for(long i=0;i*i<=x;i++){
            a=i;
        }
        return (int)a;
    }


    public static int[] plusOne(int[] digits) {
        int n = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i] += 1;
                return digits;
            } else {
                digits[i] = 0;
                n = 1;
            }
        }
        if (n == 1) {
            int[] ints = new int[digits.length + 1];
            ints[0] = 1;
            return ints;
        }
        return digits;
    }


    public static int lengthOfLastWord(String s) {
        if (s == "") return 0;
        String[] split = s.split(" ");
        return split[split.length - 1].length();
    }

    public static int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }

    public static int strStr(String haystack, String needle) {
        int s1 = haystack.length();
        int s2 = needle.length();
        if (s1 < s2) return -1;
        for (int i = 0; i <= s1 - s2; i++) {
            if (haystack.substring(i, i + s2).equals(needle)) {
                return i;
            }
        }
        return -1;
    }


    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = addTwoNumbers(l1.next, l2);
            return l1;
        } else {
            l2.next = addTwoNumbers(l1, l2.next);
            return l2;
        }

    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static boolean isValid(String s) {
        if (s == null || s.isEmpty()) return false;

        // 使用栈来跟踪开括号
        Stack<Character> stack = new Stack<>();
        // 定义括号的对应关系
        Map<Character, Character> brackets = new HashMap<>();
        brackets.put(')', '(');
        brackets.put(']', '[');
        brackets.put('}', '{');

        for (char c : s.toCharArray()) {
            // 如果是闭括号，检查栈顶是否有对应的开括号
            if (brackets.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != brackets.get(c)) {
                    return false;
                }
            } else {
                // 如果是开括号，压入栈中
                stack.push(c);
            }
        }

        // 如果栈为空，则所有括号都正确匹配
        return stack.isEmpty();
    }


    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    public static int removeDuplicates(int[] nums) {
        int k = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[k++] = nums[i];
                count = 1;
            } else {
                if (count < 2) {
                    nums[k++] = nums[i];
                }
                count++;
            }
        }
        return k;
    }

    public static int removeElement(int[] nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k++] = nums[i];
            }
        }
        System.out.println(Arrays.toString(nums));
        return nums.length - k;
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            Arrays.sort(nums1);
        }
        {
            for (int i = 0; i < n; i++) {
                nums1[m + i] = nums2[i];
            }
            Arrays.sort(nums1);
        }
        System.out.println(Arrays.toString(nums1));
    }

}
